home *** CD-ROM | disk | FTP | other *** search
/ Programmer Power Tools / Programmer Power Tools.iso / c / getf.arc / MATCH.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-11-05  |  5.7 KB  |  205 lines
  1. /*
  2.     match - test whether a file name matches a pattern
  3.  
  4.     usage...
  5.  
  6.     char pattern[10]="*alloc.c*";
  7.     char string[10]="malloc.c";
  8.     okay = match(pattern, string);
  9.  
  10.     value is nonzero if the pattern matches the string.
  11.  
  12.         *    Matches any string including the null string.
  13.         ?    Matches any single character.
  14.         [...]    Matches any one of the characters enclosed.
  15.         [~...]    Matches any character NOT enclosed.
  16.         -    May be used inside brackets to specify range
  17.             (i.e. str[1-58] matches str1, str2, ... str5, str8)
  18.         \    Escapes special characters.
  19.         Other characters match themselves.
  20.  
  21.     Unlike the wild card characters in CP/M and MS-DOS command line
  22.     interpreters, the '*' may usefully appear at the beginning of the
  23.     name...
  24.  
  25.     pattern:          *alloc
  26.     means:                    any name ending in "alloc"
  27.     matches:          alloc
  28.                       malloc
  29.                       myalloc
  30.     doesn't match:    allo
  31.                       allok
  32.                       allocate
  33.  
  34.     The pattern can usefully contain more than one '*'...
  35.  
  36.     pattern:          *ll*
  37.     means:                    any name containing "ll"
  38.     matches:          ll
  39.                       alloc
  40.                       llama
  41.                       all
  42.     doesn't match:    aloc
  43.  
  44.     Another difference is that the '.' no longer has a special meaning...
  45.  
  46.     pattern:          alloc*
  47.     means:                      any name beginning with "alloc"
  48.     matches:          alloc
  49.                       alloc.c          <-- different
  50.                       allocate.c       <-- different
  51.  
  52.  
  53.     A stressing case:   pattern <*bbbbbbbbb>
  54.                         string  <bbbbbbbbbbbbbbb>
  55.     ...uses space proportional to pattern_length and time proportional
  56.     to pattern_length*string_length.  (However, a conventional backup
  57.     type match uses time proportional to string_length**pattern_length.)
  58.  
  59.     Author:        James R. Van Zandt
  60.                 27 Spencer Dr.
  61.                 Nashua NH 03062
  62.                 <jrv@mitre-bedford.arpa>
  63.             
  64.     character set code courtesy of:
  65.     
  66.                 Gary S. Moss
  67.                 U. S. Army Ballistic Research Laboratory
  68.                 Aberdeen Proving Ground
  69.                 Maryland 21005-5066
  70.                 (301)278-6647 or AV-283-6647
  71. */
  72.  
  73. /*
  74.     If the pattern is no longer than MAX_PATTERN, the work arrays are
  75.     guaranteed to be long enough.  An uncomplicated pattern may be much
  76.     longer.  If the pattern is too long MATCH may fail to recognize
  77.     a matching string.
  78. */
  79. #define MAX_PATTERN 30
  80.  
  81. #include <stdio.h>
  82.  
  83. match(pat, nam) char *pat, *nam;
  84. {    
  85.     char **q, **a, **n, *s, *rightbrkt;
  86.     int negation;
  87.     static char 
  88.     *alive[MAX_PATTERN+2],    /* array of pointers to pattern characters which 
  89.                                 may correspond to *nam */
  90.     *next[MAX_PATTERN+2];     /* subset of above array - the pattern character
  91.                                 after a '*' has to be added */
  92. /*    alive[] and next[] are sorted by pointer value, have no duplicate entries, and
  93.     are terminated by zeros (null pointers) */
  94.  
  95. /*    printf("pattern:                     <%s >\n", pat);********/
  96.     next[0]=pat;
  97.     next[1]=0;
  98.     while(next[0])  /* there are some pattern characters that may match *nam */
  99.         {a=alive;
  100.         n=next;
  101. /********
  102.         printf("active pattern characters:    ", pat);
  103.         for (q=n, s=pat; *s || s[-1]; s++) 
  104.             if(s==*q){q++; putchar('*');}
  105.             else putchar(' ');
  106.         printf("\n");
  107.         printf("pattern pointers before expansion...\n");
  108.         for (q=n; *q; q++) printf("      %5u -> %c\n", *q, **q);
  109. *******/
  110.         while(a<=alive+MAX_PATTERN && (*a++=*n))
  111.             {/* for each '*', add the normal character which follows it
  112.                 in the pattern */
  113. /*******
  114.             printf("a=%u, checking pattern character %c\n", a, **n);
  115. ********/
  116.             if(**n=='*')
  117.                 {for (s=*n; *++s=='*'; ) {}
  118.                 if (s != n[1] && a<=alive+MAX_PATTERN) 
  119.                     *a++ = s;
  120.                 }
  121.             n++;
  122.             }
  123. /**********
  124.         printf("expanded pattern characters:  ", pat);
  125.         for (q=alive, s=pat; *s || s[-1]; s++) 
  126.             if(s==*q){q++; putchar('*');}
  127.             else putchar(' ');
  128.         printf("  =? %c\n",*nam);
  129.         printf("matching %c in name with...", *nam);
  130.         for(q=alive; *q; q++) printf("\n %5u -> %5u -> %c", q, *q, **q);        
  131.         printf(" ...%d pointers\n", q-alive);
  132. ***********/
  133.         if(*nam==0)
  134.             {/* have reached end of name... pattern matches only
  135.                 if a[-2], the last entry in alive[], points to the null
  136.                 which terminates the pattern.  (Note that a[-1] is zero.)
  137.             */
  138. /***********
  139.             printf("reached end of name, last entry is %u -> %u -> %c\n",
  140.                 a-2,a[-2], *a[-2]);
  141. ***********/
  142.             return *a[-2]==0;
  143.             }
  144.         a=alive;
  145.         n=next;
  146.         while(*a)   /* no need to limit # entries in next[], since
  147.                         there can be no more than were in alive[]  */
  148.             {switch(**a)
  149.                 {case '?':    *n++ = *a+1; break;
  150.                 case '*':    if(n[-1]!=*a) *n++ = *a; break;
  151.                 case '[':
  152.                     (*a)++;
  153.                     rightbrkt=index(*a,']');
  154.                     if(!rightbrkt){fprintf(stderr,"missing ]\n"); return 0;}
  155.                     if(**a=='~') {negation=1; (*a)++;}
  156.                     else negation=0;
  157.  
  158.                     while(*a<rightbrkt)
  159.                         {if(**a=='-' 
  160.                                 &&    (*a)[-1] != '['
  161.                                 &&    (*a)[ 1] != ']')  /* range is given */
  162.                             {if(    (*a)[-1] <= *nam
  163.                                 &&    (*a)[ 1] >= *nam) break;
  164.                             }
  165.                         else
  166.                             {if(**a=='\\') (*a)++;
  167.                             if(**a==*nam) break;
  168.                             }
  169.                         (*a)++;
  170.                         }
  171.                     if(*a!=rightbrkt ^ negation) *n++ = rightbrkt+1;
  172.                     break;
  173.                 case '\\':    (*a)++; /* escape the following character */
  174.                 default:    if(**a==*nam) *n++ = *a+1;
  175.                 }
  176.             a++;
  177.             }
  178.         *n=0;
  179.         nam++;
  180.         }
  181. /*************
  182.     printf("no pointers alive\n");
  183. **************/
  184.     return 0;  /* no match */
  185. }
  186.  
  187. #ifdef MAIN
  188.  
  189. char r[90], s[90];
  190.  
  191. main(argc, argv) int argc; char **argv;
  192. {    int dif;
  193.     while(1)
  194.         {printf("pattern > "); gets(r);
  195.         printf("name    > "); gets(s);
  196.         dif=!match(r, s);
  197.         printf("<%s> and <%s> ", r, s);
  198.         if(dif) printf("are different\n");
  199.         else printf("match\n");
  200.         if(s[0]=='q') exit();
  201.         }
  202. }
  203.  
  204. #endif
  205.